package com.example.demo.algorithm;

import java.util.Arrays;
import java.util.Random;

/**
 * 项目名称：hello-6
 * 类 名 称：MergeSort4
 * 类 描 述：归并排序
 * 创建时间：2020/12/10 20:33
 * 创 建 人：wangsheng
 */
public class MergeSort4 {


    //先定义辅助数组
    private static int[] assist;

    public static void main(String[] args) {
        //先定义要排序的数组
        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Random().nextInt(100) + 0;
        }
        assist = new int[arr.length];
        long startTime = System.currentTimeMillis();
        sort(arr, 0, arr.length - 1);
        long endTime = System.currentTimeMillis();
        long times = endTime - startTime;
        System.out.println("归并排序耗时：" + times);
        System.out.println(Arrays.toString(arr));
    }

    //对数组left到right进行拆分
    public static void sort(int[] arr, int left, int right) {
        if (right <= left) {
            return;
        } else {
            int mid = (left + right) / 2;
            //开始对左半部分进行拆分
            sort(arr, left, mid);
            //开始对右半部分进行拆分
            sort(arr, mid + 1, right);

            //开始进行归并
            merge(arr, left, mid, right);
        }

    }

    /**
     * 归并： 对left到mid和mid+1到right 进行归并
     *
     * @param arr   要排序的数组
     * @param left  最左边元素
     * @param mid   中间元素
     * @param right 最右边元素
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        //定义辅助数组的指针
        int i = left;
        //定义左边数组的指针，左边数组的第一个元素
        int p1 = left;
        //定义右边数组的指针，右边数组的第一个元素
        int p2 = mid + 1;

        //比较左边和右边的数组的各自指针对应的元素的大小
        while (p1 <= mid && p2 <= right) {
            //比较左右各自指针对应值的大小，谁小谁放到辅助数组
            if (arr[p1] < arr[p2]) {
                assist[i++] = arr[p1++];
            } else {
                assist[i++] = arr[p2++];
            }
        }

        //当某个数组(左或右)循环完毕，即上边的循环循环完毕，肯定还有一个数组还存在元素，则剩下的元素依次填充到辅助数组
        //下边的两个循环只会执行一个，因为上边while的条件是两个&&,所以只会执行一个

        //当上边循环还在满足p1<=mid时候，证明右边的已经填充完毕了，所以将p1剩下的元素赶紧填充到辅助数组
        while (p1 <= mid) {
            assist[i++] = arr[p1++];
        }
        //当上边循环还在满足p2 <= right时候，证明左边的已经填充完毕了，所以将p2剩下的元素赶紧填充到辅助数组
        while (p2 <= right) {
            assist[i++] = arr[p2++];
        }

        //现在开始从辅助数组转移到原来的arr中
        for (int index = left; index <= right; index++) {
            arr[index] = assist[index];
        }
    }

}
